// Copyright 2000-2023 JetBrains s.r.o. and contributors. Use of this source code is governed by the Apache 2.0 license.
package com.intellij.util.containers;


import com.intellij.openapi.util.Comparing;
import com.intellij.openapi.util.Condition;
import com.intellij.openapi.util.Conditions;
import com.intellij.openapi.util.Ref;
import com.intellij.util.*;
import org.jetbrains.annotations.NotNull;
import org.jetbrains.annotations.Nullable;
import org.jetbrains.annotations.Unmodifiable;

import java.util.*;
import java.util.function.Supplier;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

/**
 * An in-house and immutable version of {@code com.google.common.collect.FluentIterable}
 * with some insights from Clojure. Added bonus is that the JBIterator instances are preserved
 * during most transformations, a feature employed by {@link JBTreeTraverser}.
 * <p>
 * <p/>
 * The original JavaDoc ('FluentIterable' replaced by 'JBIterable'):
 * <p/>
 * {@code JBIterable} provides a rich interface for manipulating {@code Iterable} instances in a
 * chained fashion. A {@code JBIterable} can be created from an {@code Iterable}, or from a set
 * of elements. The following types of methods are provided on {@code JBIterable}:
 * <ul>
 * <li>chained methods which return a new {@code JBIterable} based in some way on the contents
 * of the current one (for example {@link #map})
 * <li>conversion methods which copy the {@code JBIterable}'s contents into a new collection or
 * array (for example {@link #toList})
 * <li>element extraction methods which facilitate the retrieval of certain elements (for example
 * {@link #last})
 * </ul>
 * <p/>
 * <p>Here is an example that merges the lists returned by two separate database calls, transforms
 * it by invoking {@code toString()} on each element, and returns the first 10 elements as a
 * {@code List}: <pre>   {@code
 *   JBIterable
 *       .from(database.getClientList())
 *       .filter(activeInLastMonth())
 *       .map(Functions.toStringFunction())
 *       .toList();}</pre>
 * <p/>
 * <p>Anything which can be done using {@code JBIterable} could be done in a different fashion
 * (often with {@code Iterables}), however the use of {@code JBIterable} makes many sets of
 * operations significantly more concise.
 *
 * @author Marcin Mikosik
 */
public abstract class JBIterable<E> implements Iterable<E> {

  /**
   * a Collection, an Iterable, or a single object
   */
  private final Object content;

  /**
   * Constructor for use by subclasses.
   */
  protected JBIterable() {
    content = this;
  }

  JBIterable(@NotNull E content) {
    this.content = content;
  }

  JBIterable(@NotNull Iterable<? extends E> content) {
    this.content = content;
  }

  /**
   * Lambda-friendly construction method.
   */
  public static @NotNull <E> JBIterable<E> create(@Nullable Supplier<? extends Iterator<E>> producer) {
    if (producer == null) return empty();
    return new JBIterable<E>() {
      @Override
      public @NotNull Iterator<E> iterator() {
        return producer.get();
      }
    };
  }

  /**
   * Returns a {@code JBIterable} that wraps {@code iterable}, or {@code iterable} itself if it
   * is already a {@code JBIterable}.
   *
   * @noinspection unchecked
   */
  public static @NotNull <E> JBIterable<E> from(@Nullable Iterable<? extends E> iterable) {
    if (iterable == null || iterable == EMPTY) return empty();
    if (iterable instanceof JBIterable) return (JBIterable<E>)iterable;
    if (iterable instanceof Collection && ((Collection<?>)iterable).isEmpty()) return empty();
    return new Multi<>(iterable);
  }

  private static final class Multi<E> extends JBIterable<E> {
    Multi(@NotNull Iterable<? extends E> iterable) { super(iterable); }

    @Override
    public Iterator<E> iterator() {
      return JBIterator.from(Objects.requireNonNull(asIterable()).iterator());
    }
  }

  /**
   * Returns a {@code JBIterable} that is generated by {@code generator} function applied to a previous element,
   * the first element is produced by the supplied {@code first} value.
   * Iteration stops when {@code null} is encountered.
   */
  public static @NotNull <E> JBIterable<@NotNull E> generate(@Nullable E first, @NotNull Function<? super E, ? extends E> generator) {
    if (first == null) return empty();
    return new JBIterable<E>() {
      @Override
      public Iterator<E> iterator() {
        Function<? super E, ? extends E> fun = Stateful.copy(generator);
        return new JBIterator<E>() {
          E cur = first;

          @Override
          public E nextImpl() {
            E result = cur;
            if (result == null) return stop();
            cur = fun.fun(cur);
            return result;
          }
        };
      }
    };
  }

  public static @NotNull <E> JBIterable<@NotNull E> generate(@Nullable E first1, @Nullable E first2,
                                                             @NotNull PairFunction<? super E, ? super E, ? extends E> generator) {
    if (first1 == null) return empty();
    return new JBIterable<E>() {
      @Override
      public Iterator<E> iterator() {
        return new JBIterator<E>() {
          E cur1 = first1;
          E cur2 = first2;

          @Override
          public E nextImpl() {
            E result = cur1;
            cur1 = cur2;
            cur2 = generator.fun(result, cur2);
            if (result == null) return stop();
            return result;
          }
        };
      }
    };
  }

  /**
   * Returns a {@code JBIterable} containing the one {@code element} if is not null.
   */
  public static @NotNull <E> JBIterable<@NotNull E> of(@Nullable E element) {
    if (element == null) return empty();
    return new Single<>(element);
  }

  private static final class Single<E> extends JBIterable<E> {
    Single(@NotNull E content) { super(content); }

    @Override
    public Iterator<E> iterator() { return new SingletonIterator<>(asElement()); }
  }

  /**
   * Returns a {@code JBIterable} containing {@code elements} in the specified order.
   */
  @SafeVarargs
  public static @NotNull <E> JBIterable<E> of(E @Nullable ... elements) {
    return elements == null || elements.length == 0 ? empty() : from(Arrays.asList(elements));
  }

  private static final JBIterable<?> EMPTY = new Empty();

  private static final class Empty extends JBIterable<Object> {
    @Override
    public Iterator<Object> iterator() {
      return Collections.emptyIterator();
    }
  }

  public static @NotNull <E> JBIterable<E> empty() {
    //noinspection unchecked
    return (JBIterable<E>)EMPTY;
  }

  public static @NotNull <E> JBIterable<E> once(@NotNull Iterator<? extends E> iterator) {
    return of(Ref.create(iterator)).intercept(iterator1 -> {
      Ref<? extends Iterator<? extends E>> ref = iterator1.next();
      Iterator<? extends E> result = ref.get();
      if (result == null) throw new UnsupportedOperationException();
      ref.set(null);
      return result;
    });
  }

  /**
   * Returns iterator, useful for graph traversal.
   *
   * @noinspection unchecked
   * @see TreeTraversal.TracingIt
   */
  public @NotNull <T extends Iterator<E>> T typedIterator() {
    return (T)iterator();
  }

  public final boolean processEach(@NotNull Processor<? super E> processor) {
    return ContainerUtil.process(this, processor);
  }

  public final void consumeEach(@NotNull Consumer<? super E> consumer) {
    for (E e : this) {
      consumer.consume(e);
    }
  }

  /**
   * Returns a string representation of this iterable for debugging purposes.
   */
  @Override
  public @NotNull String toString() {
    return content == this ? JBIterable.class.getSimpleName() : String.valueOf(content);
  }

  /**
   * Returns the number of elements in this iterable.
   */
  public final int size() {
    if (this == EMPTY) return 0;
    E single = asElement();
    if (single != null) return 1;
    Collection<E> col = asCollection();
    if (col != null) return col.size();
    int count = 0;
    for (E ignored : this) {
      count++;
    }
    return count;
  }

  /**
   * Returns {@code true} if this iterable contains any object for which
   * {@code equals(element)} is true.
   */
  public final boolean contains(@Nullable Object element) {
    if (this == EMPTY) return false;
    E single = asElement();
    if (single != null) return Comparing.equal(single, element);
    Collection<E> col = asCollection();
    if (col != null) return col.contains(element);
    for (E e : this) {
      if (Comparing.equal(e, element)) return true;
    }
    return false;
  }

  /**
   * Returns element at index if it is present; otherwise {@code null}
   */
  public final @Nullable E get(int index) {
    if (this == EMPTY) return null;
    E single = asElement();
    if (single != null) return index == 0 ? single : null;
    List<E> list = asRandomAccess();
    if (list != null) {
      return index >= list.size() ? null : list.get(index);
    }
    return skip(index).first();
  }

  private @Nullable List<E> asRandomAccess() {
    //noinspection CastConflictsWithInstanceof,unchecked
    return content instanceof RandomAccess ? (List<E>)content : null;
  }

  private @Nullable Collection<E> asCollection() {
    //noinspection unchecked
    return content instanceof Collection ? (Collection<E>)content : null;
  }

  @Nullable Iterable<E> asIterable() {
    //noinspection unchecked
    return content instanceof Iterable ? (Iterable<E>)content : null;
  }

  @Nullable E asElement() {
    //noinspection unchecked
    return this instanceof Single ? (E)content : null;
  }

  public final @NotNull JBIterable<E> repeat(int count) {
    return generate(this, Functions.id()).take(count).flatten(Functions.id());
  }

  /**
   * Returns a {@code JBIterable} which iterators traverse first the elements of this iterable,
   * followed by those of {@code other}. The iterators are not polled until necessary.
   */
  public final @NotNull JBIterable<E> append(@Nullable Iterable<? extends E> other) {
    if (other == null || other == EMPTY) return this;
    if (this == EMPTY) return from(other);
    Appended<E> parent = this instanceof Appended ? (Appended<E>)this : new Appended<>(this, null);
    // to keep append lazy, ignore the fact that 'other' can also be an Appended
    return new Appended<>(other, parent);
  }

  private static final class Appended<E> extends JBIterable<E> {
    final Iterable<? extends E> iterable;
    final Appended<? extends E> parent;

    Appended(@NotNull Iterable<? extends E> iterable, @Nullable Appended<? extends E> parent) {
      this.iterable = iterable;
      this.parent = parent;
    }

    @Override
    public @NotNull Iterator<E> iterator() {
      List<Iterable<? extends E>> iterables = Arrays.asList(getIterables());
      //noinspection unchecked
      return new FlattenFun.FlattenIt<E, E>(
        (Iterator<? extends E>)iterables.iterator(),
        Functions.<E, Iterable<E>>identity());
    }

    private Iterable<? extends E> @NotNull [] getIterables() {
      int size = 0;
      for (Appended<? extends E> p = this; p != null; p = p.parent) size++;
      //noinspection unchecked
      Iterable<? extends E>[] iterables = new Iterable[size];
      int i = 0;
      for (Appended<? extends E> p = this; p != null; p = p.parent) iterables[size - (++i)] = p.iterable;
      return iterables;
    }
  }

  public final @NotNull <T> JBIterable<E> append(@Nullable Iterable<? extends T> other,
                                                 @NotNull Function<? super T, ? extends Iterable<? extends E>> fun) {
    return other == null ? this :
           this == EMPTY ? from(other).flatten(fun) :
           append(from(other).flatten(fun));
  }

  /**
   * Returns a {@code JBIterable} which iterators traverse first the elements of this iterable,
   * followed by the {@code elements}.
   */
  public final @NotNull JBIterable<E> append(E @NotNull [] elements) {
    return this == EMPTY ? of(elements) : append(of(elements));
  }

  /**
   * Returns a {@code JBIterable} which iterators traverse first the elements of this iterable,
   * followed by {@code element} if it is not null.
   */
  public final @NotNull JBIterable<E> append(@Nullable E element) {
    return element == null ? this : this == EMPTY ? of(element) : append(of(element));
  }

  /**
   * Returns the elements from this iterable that satisfy a condition.
   */
  public final @NotNull JBIterable<E> filter(@NotNull Condition<? super E> condition) {
    return intercept(iterator -> JBIterator.from(iterator).filter(Stateful.copy(condition)));
  }

  /**
   * Returns the elements from this iterable that are instances of class {@code type}.
   *
   * @param type the type of elements desired
   */
  public final @NotNull <T> JBIterable<T> filter(@NotNull Class<T> type) {
    //noinspection unchecked
    return (JBIterable<T>)filter(Conditions.instanceOf(type));
  }

  public final @NotNull JBIterable<@NotNull E> filterNotNull() {
    return filter(Objects::nonNull);
  }

  public final @NotNull JBIterable<E> take(int count) {
    return intercept(iterator -> JBIterator.from(iterator).take(count));
  }

  public final @NotNull JBIterable<E> takeWhile(@NotNull Condition<? super E> condition) {
    return intercept(iterator -> JBIterator.from(iterator).takeWhile(Stateful.copy(condition)));
  }

  public final @NotNull JBIterable<E> skip(int count) {
    return intercept(iterator -> JBIterator.from(iterator).skip(count));
  }

  public final @NotNull JBIterable<E> skipWhile(@NotNull Condition<? super E> condition) {
    return intercept(iterator -> JBIterator.from(iterator).skipWhile(Stateful.copy(condition)));
  }

  /**
   * Returns a {@code JBIterable} that applies {@code function} to each element of this iterable.
   */
  public final @NotNull <T> JBIterable<T> map(@NotNull Function<? super E, ? extends T> function) {
    return intercept(iterator -> JBIterator.from(iterator).map(Stateful.copy(function)));
  }

  /**
   * A synonym for {@link JBIterable#map(Function)}.
   * Note: {@code map} is shorter and shall be preferred.
   *
   * @see JBIterable#map(Function)
   */
  public final @NotNull <T> JBIterable<T> transform(@NotNull Function<? super E, ? extends T> function) {
    return map(function);
  }

  /**
   * Returns a {@code JBIterable} that applies {@code function} to each element of this
   * iterable and concatenates the produced iterables in one.
   * Nulls are supported and silently skipped.
   */
  public @NotNull <T> JBIterable<T> flatten(@NotNull Function<? super E, ? extends Iterable<? extends T>> function) {
    return intercept(new FlattenFun<>(function));
  }

  private static final class FlattenFun<E, T> implements NotNullFunction<Iterator<? extends E>, Iterator<? extends T>> {
    final Function<? super E, ? extends Iterable<? extends T>> function;

    FlattenFun(@NotNull Function<? super E, ? extends Iterable<? extends T>> function) { this.function = function; }

    @Override
    public @NotNull Iterator<T> fun(@NotNull Iterator<? extends E> iterator) {
      return new FlattenIt<>(iterator, Stateful.copy(function));
    }

    static final class FlattenIt<E, T> extends JBIterator<T> {
      final Iterator<? extends E> original;
      final Function<? super E, ? extends Iterable<? extends T>> function;
      Iterator<? extends T> cur;

      FlattenIt(@NotNull Iterator<? extends E> iterator, @NotNull Function<? super E, ? extends Iterable<? extends T>> fun) {
        original = iterator;
        function = fun;
      }

      @Override
      public T nextImpl() {
        if (cur != null && cur.hasNext()) return cur.next();
        if (!original.hasNext()) return stop();
        Iterable<? extends T> next = function.fun(original.next());
        cur = next == null ? null : next.iterator();
        return skip();
      }
    }
  }

  /**
   * Filters out duplicate items.
   */
  public final @NotNull JBIterable<E> unique() {
    return unique(Functions.identity());
  }

  /**
   * Filters out duplicate items, where an element identity is provided by the specified function.
   */
  public final @NotNull JBIterable<E> unique(@NotNull Function<? super E, ?> identity) {
    return filter(new SCond<E>() {
      Set<Object> visited;

      @Override
      public boolean value(E e) {
        if (visited == null) visited = new java.util.HashSet<>();
        return visited.add(identity.fun(e));
      }
    });
  }

  /**
   * The most generic iterator transformation.
   */
  public final @NotNull <T> JBIterable<T> intercept(@NotNull Function<? super Iterator<? extends E>, ? extends Iterator<? extends T>> function) {
    if (this == EMPTY) return empty();
    if (this instanceof Intercepted) {
      Intercepted<E, E> intercepted = (Intercepted<E, E>)this;
      Function<Iterator<? extends E>, Iterator<? extends T>> compose = Functions.compose(intercepted.interceptor, function);
      return new Intercepted<>(intercepted.original, compose);
    }
    return new Intercepted<>(this, function);
  }

  private static final class Intercepted<E, T> extends JBIterable<T> {
    final JBIterable<? extends E> original;
    private final Function<? super Iterator<? extends E>, ? extends Iterator<? extends T>> interceptor;

    Intercepted(@NotNull JBIterable<? extends E> original,
                @NotNull Function<? super Iterator<? extends E>, ? extends Iterator<? extends T>> interceptor) {
      this.original = original;
      this.interceptor = interceptor;
    }

    @Override
    public Iterator<T> iterator() {
      //noinspection unchecked
      return (Iterator<T>)interceptor.fun(original.iterator());
    }
  }

  /**
   * Returns the first element in this iterable or null.
   */
  public final @Nullable E first() {
    if (this == EMPTY) return null;
    E single = asElement();
    if (single != null) return single;
    List<E> list = asRandomAccess();
    if (list != null) {
      return list.isEmpty() ? null : list.get(0);
    }
    Iterator<E> iterator = iterator();
    return iterator.hasNext() ? iterator.next() : null;
  }

  /**
   * Returns the first element if it is the only one, otherwise null.
   */
  public final @Nullable E single() {
    if (this == EMPTY) return null;
    E single = asElement();
    if (single != null) return single;
    List<E> list = asRandomAccess();
    if (list != null) {
      return list.size() != 1 ? null : list.get(0);
    }
    Iterator<E> iterator = iterator();
    E first = iterator.hasNext() ? iterator.next() : null;
    return iterator.hasNext() ? null : first;
  }

  /**
   * Returns the last element in this iterable or null.
   */
  public final @Nullable E last() {
    if (this == EMPTY) return null;
    E single = asElement();
    if (single != null) return single;
    List<E> list = asRandomAccess();
    if (list != null) {
      return list.isEmpty() ? null : list.get(list.size() - 1);
    }
    E cur = null;
    for (E e : this) {
      cur = e;
    }
    return cur;
  }

  /**
   * Perform calculation over this iterable.
   */
  public final <T> T reduce(@Nullable T first, @NotNull PairFunction<? super T, ? super E, ? extends T> function) {
    T cur = first;
    for (E e : this) {
      cur = function.fun(cur, e);
    }
    return cur;
  }

  /**
   * Perform calculation over this iterable.
   */
  public final E reduce(@NotNull PairFunction<? super E, ? super E, ? extends E> function) {
    boolean first = true;
    E cur = null;
    for (E e : this) {
      if (first) {
        cur = e;
        first = false;
      }
      else {
        cur = function.fun(cur, e);
      }
    }
    return cur;
  }

  /**
   * Returns the first matching element.
   */
  public final @Nullable E find(@NotNull Condition<? super E> condition) {
    return filter(condition).first();
  }

  /**
   * Returns the index of the matching element.
   */
  public final int indexOf(@NotNull Condition<? super E> condition) {
    int index = 0;
    for (E e : this) {
      if (condition.value(e)) {
        return index;
      }
      index++;
    }
    return -1;
  }

  /**
   * Synonym for {@code map(..).filter(notNull())}.
   *
   * @see JBIterable#map(Function)
   * @see JBIterable#filter(Condition)
   */
  public final @NotNull <T> JBIterable<@NotNull T> filterMap(@NotNull Function<? super E, ? extends T> function) {
    return intercept(iterator -> JBIterator.from(iterator).filterMap(Stateful.copy(function)));
  }

  /**
   * "Maps" and "flattens" this iterable.
   *
   * @see JBIterable#map(Function)
   * @see JBIterable#flatten(Function)
   */
  public final @NotNull <T> JBIterable<T> flatMap(@NotNull Function<? super E, ? extends Iterable<? extends T>> function) {
    return map(function).flatten(Functions.identity());
  }

  /**
   * Returns the iterable which elements are interleaved with the separator.
   */
  public final @NotNull JBIterable<E> join(@Nullable E separator) {
    return intercept(original -> {
      return new JBIterator<E>() {
        boolean flag;

        @Override
        protected E nextImpl() {
          if (!original.hasNext()) return stop();
          flag = !flag;
          return flag ? original.next() : separator;
        }
      };
    });
  }


  /**
   * Splits this {@code JBIterable} into iterable of lists of the specified size.
   * If 'strict' flag is true only groups of size 'n' are returned.
   */
  public final @NotNull JBIterable<@NotNull List<E>> split(int size, boolean strict) {
    return split(size).filterMap(es -> {
      List<E> list = es.addAllTo(new ArrayList<>(size));
      return strict && list.size() < size ? null : list;
    });
  }

  /**
   * Splits this {@code JBIterable} into iterable of iterables of the specified size.
   * All iterations are performed in-place without data copying.
   */
  public final @NotNull JBIterable<@NotNull JBIterable<E>> split(int size) {
    if (size <= 0) throw new IllegalArgumentException(size + " <= 0");
    return intercept(orig -> {
      return new JBIterator<JBIterable<E>>() {
        JBIterator<E> it;

        @Override
        protected JBIterable<E> nextImpl() {
          // iterate through the previous result fully before proceeding
          while (it != null && it.advance()) /* no-op */ ;
          it = null;
          return orig.hasNext() ? once((it = JBIterator.wrap(orig)).take(size)) : stop();
        }
      };
    });
  }

  public enum Split {AFTER, BEFORE, AROUND, OFF, GROUP}

  /**
   * Splits this {@code JBIterable} into iterable of iterables with separators matched by the specified condition.
   * All iterations are performed in-place without data copying.
   */
  public final @NotNull JBIterable<@NotNull JBIterable<E>> split(@NotNull Split mode, @NotNull Condition<? super E> separator) {
    return intercept(orig -> {
      Condition<? super E> condition = Stateful.copy(separator);
      return new JBIterator<JBIterable<E>>() {
        JBIterator<E> it;
        E stored;
        int st; // encode transitions: -2:sep->sep, -1:val->sep, 1:sep->val, 2:val->val

        @Override
        protected JBIterable<E> nextImpl() {
          // iterate through the previous result fully before proceeding
          while (it != null && it.advance()) /* no-op */ ;
          it = null;
          // empty case: check hasNext() only if nothing is stored to be compatible with JBIterator#cursor()
          if (stored == null && !orig.hasNext()) {
            if (st < 0 && mode != Split.BEFORE && mode != Split.GROUP) {
              st = 1;
              return empty();
            }
            return stop();
          }
          // general case: add empty between 2 separators in KEEP mode; otherwise go with some state logic
          if (st == -2 && mode == Split.AROUND) {
            st = -1;
            return empty();
          }
          E tmp = stored;
          stored = null;
          return of(tmp).append(once((it = JBIterator.wrap(orig)).takeWhile(e -> {
            boolean sep = condition.value(e);
            int st0 = st;
            st = st0 < 0 && sep ? -2 : st0 > 0 && !sep ? 2 : sep ? -1 : 1;
            boolean result;
            switch (mode) {
              case AFTER:
                result = st != -2 && (st != 1 || st0 == 0);
                break;
              case BEFORE:
                result = st != -2 && st != -1;
                break;
              case AROUND:
                result = st0 >= 0 && st > 0;
                break;
              case GROUP:
                result = st0 >= 0 && st > 0 || st0 <= 0 && st < 0;
                break;
              case OFF:
                result = st > 0;
                break;
              default:
                throw new AssertionError(st);
            }
            stored = !result && mode != Split.OFF ? e : null;
            return result;
          })));
        }
      };
    });
  }

  /**
   * Determines whether this iterable is empty.
   */
  public final boolean isEmpty() {
    if (this == EMPTY) return true;
    E single = asElement();
    if (single != null) return false;
    Collection<E> col = asCollection();
    if (col != null) {
      return col.isEmpty();
    }
    return !iterator().hasNext();
  }

  /**
   * Determines whether this iterable is not empty.
   */
  public final boolean isNotEmpty() {
    return !isEmpty();
  }

  /**
   * Collects all items into the specified collection and returns it wrapped in a new {@code JBIterable}.
   * This is equivalent to calling {@code JBIterable.from(addAllTo(c))}.
   */
  public final @NotNull JBIterable<E> collect(@NotNull Collection<E> collection) {
    return from(addAllTo(collection));
  }

  /**
   * Collects all items into an {@link ArrayList} and returns it wrapped in a new {@code JBIterable}.
   *
   * @see JBIterable#collect(Collection)
   */
  public final @NotNull JBIterable<E> collect() {
    if (content instanceof Collection) return this;
    return collect(new ArrayList<>());
  }

  /**
   * Collects all items into an {@link ArrayList}, sorts it and returns it wrapped in a new {@code JBIterable}.
   *
   * @see JBIterable#collect(Collection)
   */
  public final @NotNull JBIterable<E> sort(@NotNull Comparator<? super E> comparator) {
    ArrayList<E> list = addAllTo(new ArrayList<>());
    list.sort(comparator);
    return from(list);
  }

  /**
   * Collects all items into an immutable {@code List} and returns it.
   */
  public final @Unmodifiable @NotNull List<E> toList() {
    if (this == EMPTY) return Collections.emptyList();
    E single = asElement();
    if (single != null) return Collections.singletonList(single);
    List<E> result = ContainerUtil.newArrayList(this);
    return result.isEmpty() ? Collections.emptyList() : Collections.unmodifiableList(result);
  }

  /**
   * Collects all items into an immutable {@code Set} and returns it.
   */
  public final @NotNull Set<E> toSet() {
    if (this == EMPTY) return Collections.emptySet();
    E single = asElement();
    if (single != null) return Collections.singleton(single);
    LinkedHashSet<E> result = ContainerUtil.newLinkedHashSet(this);
    return result.isEmpty() ? Collections.emptySet() : Collections.unmodifiableSet(result);
  }

  /**
   * Synonym for {@code toList().toArray(array)}.
   *
   * @see List#toArray(Object[])
   */
  public final E @NotNull [] toArray(E @NotNull [] array) {
    if (this == EMPTY) return array;
    E single = asElement();
    if (single != null) return Collections.singletonList(single).toArray(array);
    return ContainerUtil.newArrayList(this).toArray(array);
  }

  /**
   * Returns a {@code Map} for which the keys and values are defined by the specified converters.
   * {@code {@link LinkedHashMap}} is used, so the order is preserved.
   */
  public final @NotNull <K, V> Map<K, V> toMap(@NotNull Convertor<? super E, ? extends K> toKey,
                                               @NotNull Convertor<? super E, ? extends V> toValue) {
    if (this == EMPTY) return Collections.emptyMap();
    Map<K, V> map = new LinkedHashMap<>();
    for (E e : this) map.put(toKey.convert(e), toValue.convert(e));
    return map.isEmpty() ? Collections.emptyMap() : Collections.unmodifiableMap(map);
  }

  /**
   * A synonym for {@code toMap(Convertor.SELF, toValue)}
   *
   * @see JBIterable#toMap(Convertor, Convertor)
   */
  public final @NotNull <V> Map<E, V> toMap(@NotNull Convertor<? super E, ? extends V> toValue) {
    return toMap(Convertor.self(), toValue);
  }

  /**
   * A synonym for {@code toMap(toKey, Convertor.SELF)}
   *
   * @see JBIterable#toMap(Convertor, Convertor)
   */
  public final @NotNull <K> Map<K, E> toReverseMap(@NotNull Convertor<? super E, ? extends K> toKey) {
    return toMap(toKey, Convertor.self());
  }

  public final @NotNull Stream<E> toStream() {
    return StreamSupport.stream(spliterator(), false);
  }

  /**
   * Collects all items to the specified collection and returns it.
   */
  public final @NotNull <C extends Collection<? super E>> C addAllTo(@NotNull C collection) {
    if (this == EMPTY) return collection;
    E single = asElement();
    if (single != null) {
      collection.add(single);
      return collection;
    }
    Collection<E> col = asCollection();
    if (col != null) {
      collection.addAll(col);
    }
    else {
      for (E item : this) {
        collection.add(item);
      }
    }
    return collection;
  }

  /**
   * Base class for all stateful filters and functions.
   * A separate cloned instance (shallow copy) is used for each iterator.
   * All mutable non-primitive fields <b>MUST BE</b> lazily initialized in {@link Condition#value(Object)} or {@link Function#fun(Object)} method.
   */
  public abstract static class Stateful<Self extends Stateful<?>> implements Cloneable {
    static @NotNull <T> T copy(@NotNull T o) {
      if (!(o instanceof Stateful)) return o;
      //noinspection unchecked
      return (T)((Stateful<?>)o).clone();
    }

    @Override
    public Self clone() {
      try {
        //noinspection unchecked
        return (Self)super.clone();
      }
      catch (CloneNotSupportedException e) {
        throw new AssertionError(e);
      }
    }
  }

  /**
   * Stateful {@link Conditions}.
   * A separate cloned instance (shallow copy) is used for each iterator.
   * All mutable non-primitive fields <b>MUST BE</b> lazily initialized in {@link #value(Object)} method.
   */
  public abstract static class SCond<T> extends Stateful<SCond<T>> implements Condition<T> {
  }

  /**
   * Stateful {@link Function}.
   * A separate cloned instance (shallow copy) is used for each iterator.
   * All mutable non-primitive fields <b>MUST BE</b> lazily initialized in {@link #fun(Object)} method.
   */
  public abstract static class SFun<S, T> extends Stateful<SFun<S, T>> implements Function<S, T> {
  }
}
